package cn.t222.ch07.starter;

import java.util.HashMap;
import java.util.Iterator;


public class LRU<K,V> implements Iterable<K> {
    private Node head;
    private Node tail;
    private HashMap<K, Node> dataMap;
    private int maxSize;
    public LRU(int maxSize) {
        this.maxSize = maxSize;
        this.dataMap = new HashMap<>(maxSize * 4 / 3);
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        head.prev = null;

        tail.next = null;
        tail.prev = head;
    }

    /**
     * 节点类
     */
    private class Node {
        private Node prev;
        private Node next;
        private K key;
        private V value;
        public Node(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }
    public V get(K key) {
        if (!dataMap.containsKey(key)) {
            return null;
        }

        Node node = dataMap.get(key);
        unlink(node);//移除
        appendHead(node);//加到链表头

        return node.value;
    }
    private Node removeTail() {

        Node node = tail.prev;

        Node pre = node.prev;
        tail.prev = pre;
        pre.next = tail;

        node.prev = null;
        node.next = null;

        return node;
    }
    private void appendHead(Node node) {
        Node next = head.next;
        node.next = next;
        next.prev = node;
        node.prev = head;
        head.next = node;
    }

    private void unlink(Node node) {
        Node pre = node.prev;//被删除节点的前一个节点
        Node next = node.next;//被删节点的后一个节点

        pre.next = next;//前一个节点的下一个节点为被删除元素的下一个节点
        next.prev = pre;//后一个节点的前一个节点为被删除元素的前一个节点

        node.prev = null;
        node.next = null;
    }

    @Override
    public Iterator<K> iterator() {
        return new Iterator<K>() {
            private Node cur = head.next;

            @Override
            public boolean hasNext() {
                return cur != tail;
            }

            @Override
            public K next() {
                Node node = cur;
                cur = cur.next;
                return node.key;
            }
        };
    }
    public void put(K key, V value) {

        if (dataMap.containsKey(key)) {
            Node node = dataMap.get(key);
            unlink(node);
        }

        Node node = new Node(key, value);
        dataMap.put(key, node);
        appendHead(node);

        if (dataMap.size() > maxSize) {
            Node toRemove = removeTail();
            dataMap.remove(toRemove.key);
        }
    }



    public static void main(String[] args) {
        LRU<Integer, Stu> lru = new LRU<>(5);
        lru.put(1, new Stu(1,"a"));
        lru.put(2, new Stu(2,"b"));
        lru.put(3, new Stu(3,"c"));
        lru.put(4, new Stu(4,"d"));
        lru.put(5, new Stu(5,"e"));
        print(lru);
        lru.get(3);
        print(lru);
        lru.get(5);
        print(lru);
        lru.put(6, new Stu(6,"f"));
        print(lru);
    }

    private static void print(LRU<Integer, Stu> lru) {
        Iterator<Integer> iter  = lru.iterator();
        while(iter.hasNext()) {
            System.out.println(iter.next());
        }
        System.out.println("=========================");
    }
}
